\section{Inexistence of Anonymous Nice Mechanisms for More Than 2 Facilities}
\label{s:3facilities}

We next show that for all $K \geq 3$, there are no anonymous nice mechanisms for $K$-Facility Location with $n \geq K+1$ agents.

\begin{theorem}\label{thm:3facilities}
For every $K \geq 3$, any deterministic anonymous strategyproof mechanism for $K$-Facility Location has an unbounded approximation ratio.
\end{theorem}

\begin{proof}
We only consider the case where $K = 3$ and $n = 4$. It is straightforward to verify that the proof generalizes to any $K \geq 3$ and any $n \geq K+1$.
%
For sake of contradiction, we let $F$ be an anonymous nice mechanism for $3$-Facility Location, and let $\rho$ be the approximation ratio of $F$ for instances with $4$ agents. Next, we construct a family of instances for which the approximation ratio of $F$ is greater than $\rho$.

Since $F$ is anonymous, we assume that for any instance $\vec{x}$, $x_1 < x_2 < x_3 < x_4$ (i.e. the agents are arranged on the line in increasing order of their indices).
%
For some sufficiently large $\lambda > \rho$, we consider the instance $\vec{x} = (0, \lambda, 3\lambda^2+\lambda, 3\lambda^2+\lambda+1)$, which is $(1|2|3,4)$-well-separated. By Proposition~\ref{prop:interval}, $F_3(\vec{x}) \in [x_3, x_4]$. In fact, we can assume, without loss of generality, that $F_3(\vec{x}) \in \{x_3, x_4\}$. Otherwise, if $F_3(\vec{x}) = a$ and $x_3 < a < x_4$, the instance $(\vec{x}_{-4}, a)$ is also $(1|2|3,4)$-well-separated and has $F_3(\vec{x}_{-4}, a) = a$, due to $F$'s strategyproofness.

We first consider the case where $F_3(\vec{x}) = x_4$. Since $\vec{x}$ is an $(1|2|3,4)$-well-separated instance, both $x_3$ and $x_4$ are served by the facility at $x_4$. Hence, there is a $x_3$-hole $(l, r)$ in the image set $I_3(\vec{x}_{-3})$.
%
We note that $3\lambda^2+\lambda = x_3 < r \leq x_4 = 3\lambda^2+\lambda+1$, since $x_3 \not\in F(\vec{x})$ and $x_4 \in F(\vec{x})$, and that $l \geq \lambda^2+\lambda-1$.
%
As for the latter, if $l < \lambda^2+\lambda-1$, then $y = 2\lambda^2+\lambda$ would lie in the right half of the hole $(l, r)$. Thus, if agent $3$ moves to $y$, by $F$'s strategyproofness, the nearest facility to $y$ in $F(\vec{x}_{-3}, y)$ would be at $r > 3\lambda^2+\lambda$, and thus $\cost[F(\vec{x}_{-3}, y)] > \lambda^2$. Since the optimal cost for the instance $(\vec{x}_{-3}, y)$ is $\lambda$, the approximation ratio of $F$ would be $\lambda > \rho$.

Let us now consider the instance $\vec{x}' = (\vec{x}_{-3}, l+\eps)$, where $\eps \in (0, 1]$ is chosen small enough that $l+\eps$ lies in the left half of the hole $(l, r)$ and the instance $(0, \lambda, l, l+\eps)$ is $(1|2|3,4)$-well-separated. Since $F$ is strategyproof, and since $l$ is the nearest point to $l+\eps$ in $I_3(\vec{x}_{-3})$, $l \in F(\vec{x}')$.
%
Then, we consider the instance $\vec{x}'' = (\vec{x}'_{-4}, l)$. Since $F$ is anonymous%
%
\footnote{We highlight that the agents $3$ and $4$ implicitly switch indices in $\vec{x}'$ and $\vec{x}''$. More specifically, since we require that the agents are arranged on the line in increasing order of their indices, the location of agent $3$ is $l+\eps$ in $\vec{x}'$ and $l$ in $\vec{x}''$, and the location of agent $4$ is $3\lambda^2+\lambda+1$ in $\vec{x}'$ and $l+\eps$ in $\vec{x}''$. Therefore, to argue about the outcome of $F(\vec{x}'')$ based on the outcome of $F(\vec{x}')$, we resort to the anonymity of $F$.}
%
and strategyproof, and since $l \in F(\vec{x}')$, $x''_3 = l \in F(\vec{x}'')$.
%
Moreover, by Proposition~\ref{prop:left_cover}, $x''_4 = l+\eps \in F(\vec{x}'')$, because for the $(1|2|3,4)$-well-separated instance $\vec{x}$, $F_3(\vec{x}) = x_4$, and $\vec{x}''$ is an $(1|2|3,4)$-well-separated instance with $x''_4 \leq x_4$.
%
Since both $x''_3, x''_4 \in F(\vec{x}'')$, either the agents $1$ and $2$ are served by the same facility of $F(\vec{x}'')$ or the agent $2$ is served by the facility at $l$. In both cases, $\cost[F(\vec{x}'')] \geq \lambda$. On the other hand, the optimal cost for $\vec{x}''$ is $\eps \leq 1$, and the approximation ratio of $F$ is at least $\lambda > \rho$.

The case where $F_3(\vec{x}) = x_3$ is symmetric. The details can be found in the Appendix, Section~\ref{app:s:3facilities}
\qed\end{proof}

